package com.explorati.LeetCode438.findallanagramsinastring;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 438. Find All Anagrams in a String  滑动窗口(自己做出的)
 * 
 * Given a string s and a non-empty string p, find all the start indices of p's
 * anagrams in s.
 * 
 * Strings consists of lowercase English letters only and the length of both
 * strings s and p will not be larger than 20,100.
 * 
 * The order of output does not matter.
 * 
 * Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring
 * with start index = 0 is "cba", which is an anagram of "abc". The substring
 * with start index = 6 is "bac", which is an anagram of "abc".
 * 
 * 
 * @author explorati
 *
 */
public class Solution {
	public static List<Integer> findAnagrams(String s, String p) {
		int n = s.length();
		List<Integer> res = new ArrayList<>();
		// 用freq数组记录p中元素及其出现的次数
		int[] freq = new int[256];
		for (int i = 0; i < p.length(); i++) {
			freq[p.charAt(i)]++;
		}
		// Map<Character, Integer> map = new HashMap<>();
		// // 将p中的字符存入map中
		// for (int i = 0; i < p.length(); i++) {
		// char c = p.charAt(i);
		// if (map.containsKey(c)) {
		// map.put(c, map.get(c) + 1);
		// } else {
		// map.put(c, 1);
		// }
		// }

		int l = 0, r = 0;
		while (r < n) {
			// 复制一份freq，由于每遍历一遍就会重新遍历freq
			int[] temp = Arrays.copyOf(freq, freq.length);
			// 当temp即freq中没有此元素时，越过这个字符 注意边界
			while (temp[s.charAt(l)] == 0 && l < n - 1) {
				l++;
				r++;
			}
			// count：p中元素的个数(即r向右移动的次数)，a就是做循环跳出的
			int count = p.length(), a = l;
			while (r < s.length() && count > 0 && l == a && l < s.length()) {
				// 如果freq中含有此字符，则freq--，同时count--
				if (temp[s.charAt(r)] != 0) {
					temp[s.charAt(r++)]--;
					count--;
				} else {
					//如果freq中不包含这个字符，l ++， r++
					l = l + 1;
					r = l;
				}
				// 若是已经遍历完成，则将首位置i放入res中
				if (count == 0) {
					res.add(l);
					l = l + 1;
					r = l;
				}
			}
		}
		return res;
	}

	public static void main(String[] args) {
		// String s = "cbaebabacd";
		String s = "abab";
		String p = "ab";
		List<Integer> list = findAnagrams(s, p);
		for (int i : list) {
			System.out.print(i + "  ");
		}
	}
}
